home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / arc.zoo / arclzw.c < prev    next >
C/C++ Source or Header  |  1989-01-29  |  22KB  |  805 lines
  1. /*
  2.  * $Header: arclzw.c,v 1.6 88/07/31 18:49:49 hyc Exp $
  3.  */
  4.  
  5. /*
  6.  * ARC - Archive utility - ARCLZW
  7.  * 
  8.  * Version 2.03, created on 10/24/86 at 11:46:22
  9.  * 
  10.  * (C) COPYRIGHT 1985,86 by System Enhancement Associates; ALL RIGHTS RESERVED
  11.  * 
  12.  * By:  Thom Henderson
  13.  * 
  14.  * Description: This file contains the routines used to implement Lempel-Zev
  15.  * data compression, which calls for building a coding table on the fly.
  16.  * This form of compression is especially good for encoding files which
  17.  * contain repeated strings, and can often give dramatic improvements over
  18.  * traditional Huffman SQueezing.
  19.  * 
  20.  * Language: Computer Innovations Optimizing C86
  21.  * 
  22.  * Programming notes: In this section I am drawing heavily on the COMPRESS
  23.  * program from UNIX.  The basic method is taken from "A Technique for High
  24.  * Performance Data Compression", Terry A. Welch, IEEE Computer Vol 17, No 6
  25.  * (June 1984), pp 8-19.  Also see "Knuth's Fundamental Algorithms", Donald
  26.  * Knuth, Vol 3, Section 6.4.
  27.  * 
  28.  * As best as I can tell, this method works by tracing down a hash table of code
  29.  * strings where each entry has the property:
  30.  * 
  31.  * if <string> <char> is in the table then <string> is in the table.
  32.  */
  33. #include <stdio.h>
  34. #include "arc.h"
  35.  
  36. void    putc_pak(), abort(), putc_ncr();
  37. int    getc_unp();
  38. #if    MSDOS
  39. char    *setmem();
  40. #else
  41. #ifndef __STDC__
  42. char    *memset();
  43. #endif
  44. #endif
  45.  
  46. static void    putcode();
  47. /* definitions for older style crunching */
  48.  
  49. #define FALSE    0
  50. #define TRUE     !FALSE
  51. #define TABSIZE  4096
  52. #define NO_PRED  0xFFFF
  53. #define EMPTY    0xFFFF
  54. #define NOT_FND  0xFFFF
  55.  
  56. static unsigned short inbuf;    /* partial input code storage */
  57. static int      sp;        /* current stack pointer */
  58.  
  59. struct entry {        /* string table entry format */
  60.     char            used;    /* true when this entry is in use */
  61.     unsigned char   follower;    /* char following string */
  62.     unsigned short  next;    /* ptr to next in collision list */
  63.     unsigned short  predecessor;    /* code for preceeding string */
  64. };            /* string_tab[TABSIZE];       the code string table */
  65.  
  66.  
  67. /* definitions for the new dynamic Lempel-Zev crunching */
  68.  
  69. #define BITS   12        /* maximum bits per code */
  70. #define HSIZE  5003        /* 80% occupancy */
  71. #define INIT_BITS 9        /* initial number of bits/code */
  72.  
  73. static int      n_bits;        /* number of bits/code */
  74. static int      maxcode;    /* maximum code, given n_bits */
  75. #define MAXCODE(n)      ((1<<(n)) - 1)    /* maximum code calculation */
  76. static int      maxcodemax = 1 << BITS;    /* largest possible code (+1) */
  77.  
  78. static char     buf[BITS];    /* input/output buffer */
  79.  
  80. static unsigned char lmask[9] =    /* left side masks */
  81. {
  82.  0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00
  83. };
  84. static unsigned char rmask[9] =    /* right side masks */
  85. {
  86.  0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff
  87. };
  88.  
  89. static int      offset;        /* byte offset for code output */
  90. static long     in_count;    /* length of input */
  91. static long     bytes_out;    /* length of compressed output */
  92. static long     bytes_ref;    /* output quality reference */
  93. static long     bytes_last;    /* output size at last checkpoint */
  94. static unsigned short ent;
  95.  
  96. /*
  97.  * To save much memory (which we badly need at this point), we overlay the
  98.  * table used by the previous version of Lempel-Zev with those used by the
  99.  * new version.  Since no two of these routines will be used together, we can
  100.  * safely do this.
  101.  */
  102.  
  103. extern long     htab[HSIZE];        /* hash code table   (crunch) */
  104. extern unsigned short codetab[HSIZE];    /* string code table (crunch) */
  105. static struct    entry *string_tab=(struct entry *)htab;    /* old crunch string table */
  106.  
  107. static unsigned short *prefix=codetab;    /* prefix code table (uncrunch) */
  108. static unsigned char *suffix=(unsigned char *)htab;    /* suffix table (uncrunch) */
  109.  
  110. static int      free_ent;    /* first unused entry */
  111. static int      firstcmp;    /* true at start of compression */
  112. extern unsigned char stack[HSIZE];    /* local push/pop stack */
  113.  
  114. /*
  115.  * block compression parameters -- after all codes are used up, and
  116.  * compression rate changes, start over.
  117.  */
  118.  
  119. static int      clear_flg;
  120. #define CHECK_GAP 2048        /* ratio check interval */
  121. static long     checkpoint;
  122. void            upd_tab();
  123.  
  124. /*
  125.  * the next two codes should not be changed lightly, as they must not lie
  126.  * within the contiguous general code space.
  127.  */
  128. #define FIRST   257        /* first free entry */
  129. #define CLEAR   256        /* table clear output code */
  130.  
  131. /*
  132.  * The cl_block() routine is called at each checkpoint to determine if
  133.  * compression would likely improve by resetting the code table.  The method
  134.  * chosen to determine this is based on empirical observation that, in
  135.  * general, every 2k of input data should compress at least as well as the
  136.  * first 2k of input.
  137.  */
  138.  
  139. static          void
  140. cl_block(t)            /* table clear for block compress */
  141.     FILE           *t;    /* our output file */
  142. {
  143.     checkpoint = in_count + CHECK_GAP;
  144.  
  145.     if (bytes_ref) {
  146.         if (bytes_out - bytes_last > bytes_ref) {
  147.             setmem(htab, HSIZE * sizeof(long), 0xff);
  148.             free_ent = FIRST;
  149.             clear_flg = 1;
  150.             putcode(CLEAR, t);
  151.             bytes_ref = 0;
  152.         }
  153.     } else
  154.         bytes_ref = bytes_out - bytes_last;
  155.  
  156.     bytes_last = bytes_out;    /* remember where we were */
  157. }
  158.  
  159. /*****************************************************************
  160.  *
  161.  * Output a given code.
  162.  * Inputs:
  163.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  164.  *              that n_bits =< (LONG)wordsize - 1.
  165.  * Outputs:
  166.  *      Outputs code to the file.
  167.  * Assumptions:
  168.  *      Chars are 8 bits long.
  169.  * Algorithm:
  170.  *      Maintain a BITS character long buffer (so that 8 codes will
  171.  * fit in it exactly).  When the buffer fills up empty it and start over.
  172.  */
  173.  
  174. static          void
  175. putcode(code, t)        /* output a code */
  176.     int             code;    /* code to output */
  177.     FILE           *t;    /* where to put it */
  178. {
  179.     int             r_off = offset;    /* right offset */
  180.     int             bits = n_bits;    /* bits to go */
  181.     char           *bp = buf;    /* buffer pointer */
  182.     int             n;    /* index */
  183.  
  184.     register int    ztmp;
  185.  
  186.     if (code >= 0) {    /* if a real code *//* Get to the first byte. */
  187.         bp += (r_off >> 3);
  188.         r_off &= 7;
  189.  
  190.         /*
  191.          * Since code is always >= 8 bits, only need to mask the
  192.          * first hunk on the left. 
  193.          */
  194.         ztmp = (code << r_off) & lmask[r_off];
  195.         *bp = (*bp & rmask[r_off]) | ztmp;
  196.         bp++;
  197.         bits -= (8 - r_off);
  198.         code >>= (8 - r_off);
  199.  
  200.         /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  201.         if (bits >= 8) {
  202.             *bp++ = code;
  203.             code >>= 8;
  204.             bits -= 8;
  205.         }
  206.         /* Last bits. */
  207.         if (bits)
  208.             *bp = code;
  209.         offset += n_bits;
  210.  
  211.         if (offset == (n_bits << 3)) {
  212.             bp = buf;
  213.             bits = n_bits;
  214.             bytes_out += bits;
  215.             do
  216.                 putc_pak(*bp++, t);
  217.             while (--bits);
  218.             offset = 0;
  219.         }
  220.         /*
  221.          * If the next entry is going to be too big for the code
  222.          * size, then increase it, if possible. 
  223.          */
  224.         if (free_ent > maxcode || clear_flg > 0) {
  225.             /*
  226.              * Write the whole buffer, because the input side
  227.              * won't discover the size increase until after
  228.              * it has read it. 
  229.              */
  230.             if (offset > 0) {
  231.                 bp = buf;    /* reset pointer for writing */
  232.                 bytes_out += n = n_bits;
  233.                 while (n--)
  234.                     putc_pak(*bp++, t);
  235.             }
  236.             offset = 0;
  237.  
  238.             if (clear_flg) {    /* reset if clearing */
  239.                 maxcode = MAXCODE(n_bits = INIT_BITS);
  240.                 clear_flg = 0;
  241.             } else {/* else use more bits */
  242.                 n_bits++;
  243.                 if (n_bits == BITS)
  244.                     maxcode = maxcodemax;
  245.                 else
  246.                     maxcode = MAXCODE(n_bits);
  247.             }
  248.         }
  249.     } else {        /* dump the buffer on EOF */
  250.         bytes_out += n = (offset + 7) / 8;
  251.  
  252.         if (offset > 0)
  253.             while (n--)
  254.                 putc_pak(*bp++, t);
  255.         offset = 0;
  256.     }
  257. }
  258.  
  259. /*****************************************************************
  260.  *
  261.  * Read one code from the standard input.  If EOF, return -1.
  262.  * Inputs:
  263.  *      cmpin
  264.  * Outputs:
  265.  *      code or -1 is returned.
  266.  */
  267.  
  268. static          int
  269. getcode(f)            /* get a code */
  270.     FILE           *f;    /* file to get from */
  271. {
  272.     int             code;
  273.     static int      offset = 0, size = 0;
  274.     int             r_off, bits;
  275.     unsigned char  *bp = (unsigned char *) buf;
  276.  
  277.     if (clear_flg > 0 || offset >= size || free_ent > maxcode) {
  278.         /*
  279.          * If the next entry will be too big for the current code
  280.          * size, then we must increase the size. This implies
  281.          * reading a new buffer f